//搜索插入位置
//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
//如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//请必须使用时间复杂度为 O(log n) 的算法。
//思路：二分法
//情况1：最右/最左相等->left==right
//情况2：最右插入->end=nusSize->ruturn end;
//情况3：非最右插入（最左或内部），end=mid
//细节：使用end来省略边界的条件的判断
int searchInsert(int* nums, int numsSize, int target) {
	int left, right, mid, end;
	left = 0, right = numsSize - 1, end = numsSize;
	while (left <= right) {
		mid = left + ((right - left) >> 1);
		if (target < nums[mid]) {
			end = mid;
			right = mid - 1;
		}
		else if (target > nums[mid])
			left = mid + 1;
		else
			return mid;
	}
	return end;
}